/*
ID: guoxu1
PROG: maze1
LANG: C++
*/

#include <fstream>
#include <vector>
#include <string.h>
using namespace std;

template<typename T>
inline int& at( T* list, int r, int c )
{
	return list[ r * 64 + c ];
}

inline bool wall( char c )
{
	return ( c != ' ' );
}

struct POINT
{
	int row;
	int col;
	int value;
	
	POINT( int _row, int _col, int _value ):row(_row), col(_col), value(_value)
	{}
};

class Maze
{
public:
	int _row;
	int _col;
	int* _data;
	vector<POINT> _tasks;
	
	enum Direction
	{
		UP = 0x01,
		DOWN = 0x02,
		LEFT = 0x04,
		RIGHT = 0x08
	};
	
	enum Visited
	{
		VISITED = 0x10,
	};
	
public:
	Maze( int row, int col ):_row( row ), _col( col )
	{
		_data = new int[ row * ( 1 << 6 ) ];
		memset( _data, 0, sizeof(int) * row * ( 1 << 6 ) );
	}
	
	~Maze()
	{
		delete[] _data;
	}
	
	void Parse( int row, const char* str )
	{
		if( row % 2 == 0 )
		{
			int up = row / 2 - 1;
			int down = row / 2;
			for( int i = 0; i < _col; i++ )
			{
				if( up >= 0 && up < _row && wall( str[ i * 2 + 1 ] ) ) at( _data, up, i ) |= DOWN;
				if( down >= 0 && down < _row && wall( str[ i * 2 + 1 ] ) ) at( _data, down, i ) |= UP;
			}
		}
		else
		{
			row = ( row - 1 ) / 2;
			for( int i = 0; i <= _col; i++ )
			{
				if( wall ( str [ i * 2 ] ) )
				{
					if( i != 0 ) at( _data, row, i - 1 ) |= RIGHT;
					if( i != _col ) at( _data, row, i ) |= LEFT;
				}
			}
		}
	}
	
	void MarkExit( int row, int col, Direction d )
	{
		_tasks.push_back( POINT( row, col, 1 ) );
		at( _data, row, col ) |= VISITED;
		at( _data, row, col ) |= d;
	}
	
	int Find()
	{
		for( int i = 0; i < _col; i++ )
		{
			if( ( at( _data, 0, i ) & UP ) == 0 ) MarkExit( 0, i, UP );
			if( ( at( _data, _row - 1, i ) & DOWN ) == 0 ) MarkExit( _row - 1, i, DOWN );
		}
		
		for( int i = 0; i < _row; i++ )
		{
			if( ( at( _data, i, 0 ) & LEFT ) == 0 ) MarkExit( i, 0, LEFT );
			if( ( at( _data, i, _col - 1 ) & RIGHT ) == 0 ) MarkExit( i, _col - 1, RIGHT );
		}
		
		size_t t = 0;
		
		while( t < _tasks.size() )
		{
			POINT pt = _tasks[t++];
			if( ( at( _data, pt.row, pt.col ) & UP ) == 0 && ( at( _data, pt.row - 1, pt.col ) & VISITED ) == 0 )
			{
				_tasks.push_back( POINT( pt.row - 1, pt.col, pt.value + 1 ) );
				at( _data, pt.row - 1, pt.col ) |= VISITED;
			}
			if( ( at( _data, pt.row, pt.col ) & DOWN ) == 0 && ( at( _data, pt.row + 1, pt.col ) & VISITED ) == 0 )
			{
				_tasks.push_back( POINT( pt.row + 1, pt.col, pt.value + 1 ) );
				at( _data, pt.row + 1, pt.col ) |= VISITED;
			}
			if( ( at( _data, pt.row, pt.col ) & LEFT ) == 0 && ( at( _data, pt.row, pt.col - 1 ) & VISITED ) == 0 )
			{
				_tasks.push_back( POINT( pt.row, pt.col - 1, pt.value + 1 ) );
				at( _data, pt.row, pt.col - 1 ) |= VISITED;
			}
			if( ( at( _data, pt.row, pt.col ) & RIGHT ) == 0 && ( at( _data, pt.row, pt.col + 1 ) & VISITED ) == 0 )
			{
				_tasks.push_back( POINT( pt.row, pt.col + 1, pt.value + 1 ) );
				at( _data, pt.row, pt.col + 1 ) |= VISITED;
			}			
		}
		
		int max = 0;
		for( size_t i = 0; i < _tasks.size(); i++ )
		{
			if( max < _tasks[i].value ) max = _tasks[i].value;
		}
		return max;
	}
};

#define cin fin
#define cout fout

int main()
{
	ifstream fin( "maze1.in" );
	ofstream fout( "maze1.out" );
	
	int col = 0, row = 0;
	cin >> col >> row;
	
	Maze maze( row, col );
	
	string l;
	getline( cin, l );
	for( int i = 0; i < row * 2 + 1; i++ )
	{
		getline( cin, l );
		maze.Parse( i, l.c_str() );
	}
	
	cout << maze.Find() << endl;
	return 0;
}